#include <iostream>
#include <vector>
#include "lib/binary_tree.h"
using namespace std;

bool isSubTreeCore(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root2 == nullptr) {
    return true;
  }
  if (root1 == nullptr) {
    return false;
  }
  if (root1->value != root2->value) {
    return false;
  } else {
    return isSubTreeCore(root1->left, root2->left) && isSubTreeCore(root1->right, root2->right);
  }
}

bool isSubTree(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (!root1 && !root2) return true;
  if (!root1 || !root2) return false;
  if (isSubTreeCore(root1, root2)) return true;
  return isSubTree(root1->left, root2) || isSubTree(root1->right, root2);
}

int main() {
  vector<int> vec_a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
  vector<int> vec_b = {2, 4, 5, 8, 9};
  vector<int> vec_c = {2, 5, 5, 8, 9};
  BinaryTreeNode* root_a = CreateBinaryTree(vec_a);
  BinaryTreeNode* root_b = CreateBinaryTree(vec_b);
  BinaryTreeNode* root_c = CreateBinaryTree(vec_c);
  bool ret = isSubTree(root_a, root_b);
  cout << "b is the subtree of a: " << ret << endl;
  ret = isSubTree(root_a, root_c);
  cout << "c is the subtree of a: " << ret << endl;

  return 0;
}
